/**
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 */

/**
 * @param {number} amount
 * @param {number[]} coins
 * @param {number} coinsLength
 * @param {Map<number, number>} memory
 * @return {number}
 */
function dfs(amount, coins, coinsLength, memory) {
  if (memory.has(amount)) {
    return memory.get(amount);
  }
  let lastUsefulIndex = coinsLength - 1;
  for (; lastUsefulIndex >= 0; lastUsefulIndex -= 1) {
    if (coins[lastUsefulIndex] <= amount) {
      break;
    }
  }
  if (lastUsefulIndex < 0) {
    memory.set(amount, -1);
    return -1;
  }
  if (coins[lastUsefulIndex] === amount) {
    memory.set(amount, 1);
    return 1;
  }
  let min = Infinity;
  for (let i = lastUsefulIndex; i >= 0; i -= 1) {
    const rest = amount - coins[i];
    const count = dfs(rest, coins, rest >= coins[lastUsefulIndex] ? (lastUsefulIndex + 1) : lastUsefulIndex, memory);
    if (count !== -1) {
      min = Math.min(min, count);
    }
  }
  if (min < Infinity) {
    memory.set(amount, min + 1);
    return min + 1;
  }
  memory.set(amount, -1);
  return -1;
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
  if (!amount) {
    return 0;
  }
  coins.sort((a, b) => a - b);
  const memory = new Map();
  return dfs(amount, coins, coins.length, memory);
}

console.log(coinChange([1, 2, 5], 11) === 3);
console.log(coinChange([2], 3) === -1);
console.log(coinChange([1], 0) === 0);
